package com.zto.sch.advance.algorithms.nowcoder.offer;

import org.junit.Test;

/**
 * @program: sch-diy-parent
 * @description: 描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。
 * 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
 * @author: sch
 * @create: 2021-07-12 21:11
 **/


/**
 * 思路：
 * 台阶为1 -- 1 f(1) = 1;
 * 台阶为2 -- 2 f(2) = 2
 * 台阶为3:
 * 跳一级，余下的台阶是2，有f(2)种可能
 * 跳二级，余下的台阶是1，有f(1)种可能
 * 所以f(3) = f(1) + f(2)
 * 台阶为4：
 * f(4) = f(3) + f(2)
 * ...
 * f(n)=f(n-1)+f(n-2);
 */
public class 跳台阶 {

    /**
     * 方法1：递归
     * 时间复杂度：O(2^n)
     * 空间复杂度：递归栈的空间
     */
    @Test
    public void testRecursion() {
        int target = 100;
        int count = getJumpCount2(target);
        System.out.println("台阶数:" + target + ",跳法:" + count);

    }

    /**
     * 方法2：递归优化--记忆化搜索
     * 思路：把计算后的保存下来
     * 建一个数组:把已计算的后的i台阶记录在arr[i]中，下次用到i台阶跳法时直接取arr[i]。
     * 怎么存：
     * 先把arr[n] = f(n-1)+f(n-2);然后返回arr[n],
     * 若arr[n] != 0 则直接返回arr[0]
     * <p>
     * 补：方法递归内存图解：
     * 如：f(n) = f(n-1)+f(n-2);会员先把f(n-1)的方法调用链执行完，弹栈后。再执行f(n-2)的方法
     * 例：f(4)=f(3)+f(2) [这个f(2)方法会最后执行]
     * f(3)=f(2)+f(1)
     * 程序执行顺序，f(3)->f(2)->f(1) -->f(2)
     * <p>
     * <p>
     * 时间复杂度：O（n）没有重复的计算
     * 空间复杂度：O（n）+ 递归栈的空间
     */
    @Test
    public void test2() {
        int target = 4;
        int[] arr = new int[40];
        int count = getJumpCount3(target, arr);
        System.out.println("台阶数:" + target + ",跳法:" + count);

    }

    /**
     * 方法3：动态规划
     * 只需用3个变量即可
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    @Test
    public void test3() {
        int target = 100;
        long count = getJumpCount4(target);
        System.out.println("台阶数:" + target + ",跳法:" + count);

    }

    private long getJumpCount4(int target) {
        long a = 1;
        long b = 2;
        long c = 0;

        if (target <= 2) {
            return target;
        }
        for (int i = 3; i <= target; i++) {
            c = a + b;
            a = b;
            b = c;
        }

        return c;
    }

    private int getJumpCount3(int target, int[] arr) {
        if (target <= 2) {
            return target;
        }

        if (arr[target] != 0) {
            return arr[target];
        }

        arr[target] = getJumpCount3(target - 1, arr) + getJumpCount3(target - 2, arr);
        return arr[target];
    }


    private int getJumpCount2(int target) {
        if (target <= 2) {
            return target;
        }
        return getJumpCount2(target - 1) + getJumpCount2(target - 2);
    }
}
